package Stack;

import java.util.Stack;

//接雨水，单调栈经典应用
public class TrappingRain {
    public static void main(String[] args) {
        int[] heights = {4,2,0,3,2,5};
        System.out.println(getAns(heights));
    }

    public static int getAns(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int[] s = new int[heights.length];
        int ans = 0;
        int curPeak = 0;
        for(int i = 0; i < heights.length; i++) {
//            while(!stack.isEmpty() && heights[stack.peek()] <= heights[i]) {
//                int index = stack.pop();
//                int h = heights[index];
//                int peekIndex = stack.isEmpty() ? -1 : stack.peek();
//                int smaller = Math.min(heights[i], peekIndex == - 1 ? h : heights[peekIndex]);
//                ans += (i - peekIndex - 1) * (smaller - h);
//            }
//            stack.push(i);

            while(curPeak != 0 && heights[s[curPeak - 1]] <= heights[i]) {
                int index = s[--curPeak];
                int h = heights[index];
                int peekIndex = curPeak == 0 ? -1 : s[curPeak - 1];
                int smaller = Math.min(heights[i], peekIndex == - 1 ? h : heights[peekIndex]);
                ans += (i - peekIndex - 1) * (smaller - h);
            }
            s[curPeak++] = i;
        }
        return ans;
    }
}
